// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2021-12-07 19:52
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.DataStruct.Tree.TwoBinaryTree;

import java.util.*;

@SuppressWarnings({"all"})
public class Utils {
    // 实现树的先序遍历
    public void preSearch(TreeNode root) {
        if (root == null) {
            System.out.print("null\t");
            return;
        }
        System.out.print(root.val + "\t");
        preSearch(root.left);
        preSearch(root.right);
    }

    // 实现树的中序遍历
    public void midSearch(TreeNode root) {
        if (root != null) {
            midSearch(root.left);
            System.out.print(root.val + "\t");
            midSearch(root.right);
        }
    }

    // 实现树的后序遍历
    public void posSearch(TreeNode root) {
        if (root == null) {
            return;
        }
        preSearch(root.left);
        preSearch(root.right);
        System.out.println(root.val);
    }

    // 实现树的构造
    // 1 使用前序和中序序列构造二叉树

    /**
     * 通过前序序列确定二叉树的根节点
     * 通过中序序列确定二叉树左子树和右子树位置
     * 前序序列的第一个元素是二叉树的根节点
     * 通过Map存储二叉树节点信息
     */
    public TreeNode preInOrederBuildTree(int[] pre, int[] in) {
        Map inMap = toMap(in);
        TreeNode root = buildTree(pre, inMap, 0, pre.length - 1, 0);
        return root;
    }


    /**
     * 前序中序序列构造二叉树
     *
     * @param pre     前序序列数据
     * @param in      中序序列数据
     * @param start   前序序列起点
     * @param end     前序序列终点
     * @param instart 中序序列起点
     * @return
     */
    protected TreeNode buildTree(int[] pre, Map<Integer, Integer> in, int start, int end, int instart) {
        // 递归结束条件
        if (start > end) {
            return null;
        }
        // 获取中序序列中根节点索引
        int rootIndex = in.get(pre[start]);
        // 确定树的左子树和右子树的长度
        int leftLen = rootIndex - instart;
        // 创建节点
        TreeNode root = new TreeNode<>();
        root.val = pre[start];
        // 递归创建
        root.left = buildTree(pre, in, start + 1, start + leftLen, instart);
        root.right = buildTree(pre, in, start + leftLen + 1, end, rootIndex + 1);
        if (root.left != null) {
            root.left.parent = root;
        }
        if (root.right != null) {
            root.right.parent = root;
        }
        return root;
    }

    // 实现将数据转换为Map结构存储
    // 为了实现从前序序列定位中序序列根节点的位置
    public Map toMap(int[] data) {
        if (data.length == 0) {
            return null;
        }
        Map<Integer, Integer> dataMap = new HashMap<>();
        for (int i = 0; i < data.length; i++) {
            dataMap.put(data[i], i);
        }

        return dataMap;
    }

    // 2 通过中序和后序序列构造二叉树
    public TreeNode constructTreeByInPos(int[] in, int[] pos) {
        Map map = toMap(in);
        TreeNode root = inPosOrder(map, pos, 0, pos.length - 1, pos.length - 1);
        return root;
    }

    public TreeNode inPosOrder(Map<Integer, Integer> inMap, int[] pos, int start, int end, int inend) {
        // 递归结束条件
        if (start > end) {
            return null;
        }
        // 获取根节点在中序序列中的索引
        int rootIndex = inMap.get(pos[end]);
        // 获取右子树数据长度
        int rightLen = inend - rootIndex;
        // 构造节点，后序序列的最后一个数字是根节点数值
        TreeNode<Integer> root = new TreeNode<>();
        root.val = pos[end];
        // 递归构造
        root.left = inPosOrder(inMap, pos, start, end - rightLen - 1, rootIndex - 1);
        root.right = inPosOrder(inMap, pos, end - rightLen, end - 1, inend);
        if (root.left != null) {
            root.left.parent = root;
        }
        if (root.right != null) {
            root.right.parent = root;
        }
        return root;
    }

    // 方法实现查找a在Array数组数组的索引,假设a在数组中唯一存在
    public int getIndex(int a, int[] Array) {
        for (int i = 0; i < Array.length; i++) {
            if (a == Array[i]) {
                return i;
            }
        }
        System.out.println(a + "不存在数组中！");
        return -1;
    }

    // 递归建立一颗完全二叉树,传入的数据形式为整形数组
    public TreeNode constructTreeByInt(int[] treedata, int i) {
        if (i >= treedata.length) {
            return null;
        }
        TreeNode root = new TreeNode();
        root.val = treedata[i];
        root.left = constructTreeByInt(treedata, 2 * i + 1);
        root.right = constructTreeByInt(treedata, 2 * i + 2);
        return root;
    }

    /**
     * 实现树的前序非递归遍历
     *
     * @param root 需要遍历树的根节点
     *             使用辅助栈存放节点信息
     *             首先遍历完树的左节点，遍历完之后一次取出存储在栈中的节点
     *             使用while实现右节点
     *             当栈和p节点指针都为空的时候，遍历完成
     */
    public void nopreRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        // 辅助栈，存放根节点
        Stack<TreeNode> auxiliaryStack = new Stack<>();
        // 遍历指针
        TreeNode<Integer> p = root;
        // 只要p或者栈未空，则树还没有遍历完
        while (p != null || !auxiliaryStack.isEmpty()) {
            // 遍历根节点左节点
            while (p != null) {
                System.out.print(p.val + "\t");
                auxiliaryStack.push(p);
                p = p.left;
            }
            // 遍历完所有左边节点之后，取出存储在栈中的节点
            // 一次实现右节点的遍历
            if (!auxiliaryStack.isEmpty()) {
                p = auxiliaryStack.pop();
                p = p.right;
            }
        }
    }

    /**
     * 实现树的中序非递归遍历
     *
     * @param root 需要遍历的树的根节点
     *             需要找到树的最左节点，然后一次访问其父节点和父节点的右节点
     *             需要使用辅助栈存储节点信息
     */
    public void noinRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        // 辅助栈，存放根节点
        Stack<TreeNode> auxiliaryStack = new Stack<>();
        // 遍历指针
        TreeNode<Integer> p = root;
        while (p != null || !auxiliaryStack.isEmpty()) {
            // 找到树的最左节点
            while (p != null) {
                auxiliaryStack.push(p);
                p = p.left;
            }
            if (!auxiliaryStack.isEmpty()) {
                p = auxiliaryStack.pop();
                System.out.print(p.val + "\t");
                p = p.right;
            }
        }


    }

    /**
     * 实现树的后序非递归遍历
     *
     * @param root 需要遍历的树的根节点
     *             使用一个辅助栈，通过判断栈顶元素出现的次数实现后序遍历
     *             需要使用辅助变量isFirst
     */
    public void noposRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        // 辅助栈，存放根节点
        Stack<TreeNode> auxiliaryStack = new Stack<>();
        // 遍历指针
        TreeNode<Integer> p = root;
        while (p != null || !auxiliaryStack.isEmpty()) {
            // 找到树的最左节点
            while (p != null) {
                auxiliaryStack.push(p);
                p = p.left;
            }
            if (!auxiliaryStack.isEmpty()) {
                p = auxiliaryStack.pop();
                if (p.isFirst) {
                    p.setFirst();
                    auxiliaryStack.push(p);
                    p = p.right;
                } else {
                    // 栈顶元素为第二次出现
                    // 当栈顶元素为第二次进栈的时候说明已经将树的右子树访问完毕
                    System.out.print(p.val + "\t");
                    // 需要将p置为空，防止三次进栈
                    p = null;
                }
            }

        }
    }

    /**
     * 树的后序非递归遍历的第二种思路
     * 使用前指针判断节点的左右指针是否被访问过
     */
    public void noPosRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        // 辅助栈，存放根节点
        Stack<TreeNode> auxiliaryStack = new Stack<>();
        // 初始化指针
        TreeNode<Integer> cur = null;
        TreeNode<Integer> pre = null;
        // pre 节点跟随左右节点的步伐
        auxiliaryStack.push(root);
        while (!auxiliaryStack.isEmpty()) {
            cur = auxiliaryStack.peek();
            if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) {
                // 当访问到根节点或者当前节点的子节点全部访问后，直接输出
                System.out.print(auxiliaryStack.pop().val + "\t");
                pre = cur;
            } else {
                // 入栈之前需要判断是否为空，防止空指针异常
                if (cur.right != null) {
                    auxiliaryStack.push(cur.right);
                }
                if (cur.left != null) {
                    auxiliaryStack.push(cur.left);
                }
            }

        }
    }

    /**
     * 实现二叉树的层次遍历
     * 使用辅助队列
     *
     * @param root
     */
    public void levelOrderTravel(TreeNode root) {
        // 初始化辅助队列
        Queue<TreeNode> auxiliaryQueue = new LinkedList<>();
        auxiliaryQueue.add(root);
        while (!auxiliaryQueue.isEmpty()) {
            TreeNode tmpNode = auxiliaryQueue.element();
            // 孩子按顺序入队列
            if (tmpNode.left != null) {
                auxiliaryQueue.add(tmpNode.left);
            }
            if (tmpNode.right != null) {
                auxiliaryQueue.add(tmpNode.right);
            }
            System.out.print(auxiliaryQueue.poll().val + "\t");
        }

    }


    /**
     * 层次遍历获取树的高度
     */
    private int getHigh(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int layer = 1;
        int nlayer = 0;
        int h = 0;
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            layer--;
            if (tmp.left != null) {
                queue.offer(tmp.left);
                nlayer++;
            }
            if (tmp.right != null) {
                queue.offer(tmp.right);
                nlayer++;
            }
            if (layer == 0) {
                h++;
                layer = nlayer;
                nlayer = 0;
            }
        }
        return h;
    }

    /**
     * 实现二叉树的孩子兄弟转化
     * 需要使用辅助栈
     */
    public TreeNode biToSiblingTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Stack<TreeNode> auxiliaryStack = new Stack<>();
        auxiliaryStack.push(root);
        TreeNode p = root;
        TreeNode q = null;
        while (!auxiliaryStack.isEmpty()) {
            // 从最左叶子节点开始，思路是树的连线法
            while (p != null) {
                auxiliaryStack.push(p);
                p = p.left;
            }
            p = auxiliaryStack.peek();
            if (p.right != null) {
                p.left = p.right;
                p = p.left;
            } else {
                auxiliaryStack.pop();
                // 避免出现根节点出栈之后出现空指针异常
                if (auxiliaryStack.isEmpty()) {
                    return root;
                }
                // 此时的栈顶节点为当前节点的父节点
                q = auxiliaryStack.peek();
                // 如果当前节点的父节点有右子树，则将右子树连给当前节点，并且对父节点的右子树实现连线操作
                if (q.right != null) {
                    p.right = q.right;
                    q.right = null;
                    p = p.right;
                } else {
                    p = null;
                }
            }
        }
        return root;
    }


    /**
     * 复制一颗二叉树
     *
     * @param root 原二叉树的根节点
     * @return 返回新创建的二叉树
     * 一边遍历，一边创建节点并且连线
     */
    public TreeNode dupblicateBiTree(TreeNode root) {
        if (root != null) {
            TreeNode newRoot = new TreeNode();
            newRoot.val = root.val;
            newRoot.left = dupblicateBiTree(root.left);
            newRoot.right = dupblicateBiTree(root.right);
            return newRoot;
        }
        return null;
    }

    /**
     * 由数组创建一个二插排序树
     * 遍历数组，以第一个元素为根节点，其他元素小于根节点的在根节点左边，大于根节点的在根节点右边
     * 需要辅助指针，每次遍历一个数据的时候需要比较当前指针q的值和当前数据的大小
     * 1 相等(暂时不考虑)
     * 插入左右子树都可以
     * 2 小于
     * 继续和p的左子树比较
     * p = p.left
     * 3 大于
     * 继续和p的右子树比较
     * p = p.right
     * <p>
     * 方法时间复杂度
     * O(nlgn)
     */
    public TreeNode constructSortTree(int[] data) {
        if (data.length == 0) {
            // 传入的数组为空
            return null;
        }
        TreeNode<Integer> root = new TreeNode<>();
        TreeNode<Integer> p = new TreeNode<>();
        root.val = data[0];

        for (int i = 1; i < data.length; i++) {
            // 每插入一个节点都需要遍历已经创建的树
            p = root;
            while (true) {
                if (p.val >= data[i]) {
                    if (p.left != null) {
                        p = p.left;
                    } else {
                        // 如果节点的左子树为空，则将小于当前节点的值置于左子树
                        TreeNode<Integer> node = new TreeNode<>();
                        node.val = data[i];
                        p.left = node;
                        node.parent = p;
                        break;
                    }
                } else if (p.val < data[i]) {
                    if (p.val < data[i]) {
                        if (p.right != null) {
                            p = p.right;
                        } else {
                            // 如果节点的右子树为空，则将大于当前节点的值置于右子树
                            TreeNode<Integer> node = new TreeNode<>();
                            node.val = data[i];
                            p.right = node;
                            node.parent = p;
                            break;
                        }
                    } else {
                        System.out.println("Equals!");
                    }
                }
            }
        }
        return root;
    }
    /**
     * 将一棵二叉树转化为二插排序树
     *      转化为数组再进行创建
     *      算法时间复杂度：
     *          O(2*n*lgn)
     */
    /**
     * 将一棵二插树转化为严格二叉树
     */


    /**
     * 寻找排序二叉树的的最小值
     * 时间复杂度：
     * O(lgn)
     */
    public int getMinimum(TreeNode<Integer> root) {
        if (root == null) {
            System.out.println("传入的树为空！");
            return -1;
        }
        TreeNode<Integer> tmp = root;
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        return tmp.val;
    }

    /**
     * 寻找排序二叉树的的最大值
     * 时间复杂度：
     * O(lgn)
     */
    public int getMaximum(TreeNode<Integer> root) {
        if (root == null) {
            System.out.println("传入的树为空！");
            return -1;
        }
        TreeNode<Integer> tmp = root;
        while (tmp.right != null) {
            tmp = tmp.right;
        }
        return tmp.val;
    }

    /**
     * 寻找排序二叉树的的最小值
     * 递归版本
     * 时间复杂度：
     * O(lgn)
     */
    public TreeNode getMinimumByRecursion(TreeNode<Integer> root) {
        if (root == null) {
            // 抵达叶子节点或者传入的节点为空节点
            return null;
        } else if (root.left != null) {
            return getMinimumByRecursion(root.left);
        } else {
            return root;
        }
    }


    /**
     * 寻找排序二叉树的的最大值
     * 递归版本
     * 时间复杂度：
     * O(lgn)
     */
    public TreeNode getMaximumByRecursion(TreeNode<Integer> root) {
        if (root == null) {
            // 抵达叶子节点或者传入的节点为空节点
            return null;
        } else if (root.right != null) {
            return getMaximumByRecursion(root.right);
        } else {
            return root;
        }
    }

    /**
     * 返回二叉排序树中指定节点的后继节点
     * 1 当前节点的右子树不为空：
     * 当前节点的后继节点为当前节点右子树的最左节点
     * 2 当前节点的右子树为空
     * 当前节点的后继节点为当存在当前节点的祖先节点为其祖先节点的父节点的左子树时候
     * 的祖先节点的父节点
     *
     * @param root
     * @return 返回后继节点
     */
    public TreeNode<Integer> TREE_SUCCESSOR(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.right != null) {
            // 当前节点存在右子树
            return getMinimumByRecursion(root.right);
        } else {
            // 当前节点不存在右子树
            // 初始化建立指针
            TreeNode<Integer> cur = root;
            TreeNode<Integer> parent = cur.parent;
            while (parent != null && cur == parent.right) {
                parent = parent.parent;
                cur = cur.parent;
            }
            // 此时cur为parent的左子树，当查询的节点为树中的最右节点，此时的parent节点为根节点
            return parent;
        }
    }

    /**
     * 返回二叉排序树中指定节点的前继节点
     * 1 当前节点的左子树不为空：
     * 当前节点的后继节点为当前节点右子树的最左节点
     * 2 当前节点的左子树为空
     * 当前节点的前继节点为当存在当前节点的祖先节点为其祖先节点的父节点的右子树时候
     * 的祖先节点的父节点
     *
     * @param root
     * @return 返回后继节点
     */
    public TreeNode<Integer> TREE_PREDECESSOR(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            // 当前节点存在左子树
            return getMaximumByRecursion(root.left);
        } else {
            // 当前节点不存在左子树
            // 初始化建立指针
            TreeNode<Integer> cur = root;
            TreeNode<Integer> parent = cur.parent;
            while (parent != null && cur == parent.left) {
                parent = parent.parent;
                cur = cur.parent;
            }
            // 此时cur为parent的左子树，当查询的节点为树中的最右节点，此时的parent节点为根节点
            return parent;
        }


    }

    /**
     * 实现二插排序树的插入
     *
     * @param root       待插入的树
     * @param insertNode 待插入的节点
     * @return 返回一个布尔类型的数据
     */
    public void sortTreeInsert(TreeNode<Integer> root, TreeNode<Integer> insertNode) {
        if (root == null) {
            // 传入的树为空树
            root = insertNode;
        }
        // 因为树的结构中定义有父节点，所以插入的时候需要指针定位父节点
        TreeNode<Integer> x = root;
        TreeNode<Integer> y = null;
        while (x != null) {
            y = x;
            if (x.val > insertNode.val) {
                // 要插入的地方在当前值的左边
                x = x.left;
            } else {
                // 要插入的地方在当前值的右边
                x = x.right;
            }
        }
        insertNode.parent = y;
        if (y.val > insertNode.val) {
            y.left = insertNode;
        } else {
            y.right = insertNode;
        }
    }

    /**
     * 实现二插排序树节点的删除
     *
     * @param root       待删除树
     * @param deleteNode 待删除节点
     *                   1 左孩子节点为空
     *                   使用右孩子节点代替被删除节点
     *                   2 右孩子节点为空
     *                   使用左孩子节点代替被删除节点
     *                   3 两个孩子节点不为空
     *                   寻找当前节点的后继节点，并且transplant
     *                   需要判断后继节点是不是要删除节点的右孩子节点
     *                   如果是右孩子节点则直接transplant
     *                   如果不是右孩子节点，需要处理后继节点的相关关系
     *                   transplant 可能会删除节点的孩子信息
     */
    public void deleteSortTree(TreeNode root, TreeNode deleteNode) {
        if (deleteNode.left == null) {
            // 删除节点的左孩子节点为空,直接用删除节点的右孩子节点代替当前节点
            // 即使删除节点的右孩子节点为空
            // 因为左孩子节点为空，所以transplant并没有误删节点的孩子信息
            TRANSPLANT(root, deleteNode, deleteNode.right);
        } else if (deleteNode.right == null) {
            // 删除节点的右孩子节点为空，直接使用删除节点的左孩子节点代替当前节点
            // 因为右孩子节点为空，所以transplant并没有误删节点信息
            TRANSPLANT(root, deleteNode, deleteNode.right);
        } else {
            // 删除节点的两个孩子节点都不为空
            TreeNode<Integer> y = TREE_SUCCESSOR(deleteNode);
            if (y != deleteNode.right) {
                // 后继节点并不是删除节点的右孩子节点
                // 需要保留后继节点的孩子信息
                // 因为删除节点的后继节点一定没有左孩子节点，所以这里的transplant并不会误删孩子节点信息
                TRANSPLANT(root, y, y.right);
                y.right = deleteNode.right;
                deleteNode.right.parent = y;
            }
            // 这里处理删除节点的左孩子信息
            y.left = deleteNode.left;
            deleteNode.left.parent = y;
        }
    }


    /**
     * 使用一颗子树替换一颗子树并成为其双亲节点的子节点
     *
     * @param root 替换节点的树
     * @param u    被替换的节点
     * @param v    替换的子树
     */
    public void TRANSPLANT(TreeNode<Integer> root, TreeNode u, TreeNode v) {
        if (root == null) {
            System.out.println("There is no element in Tree!");
            return;
        } else if (u == root) {
            // 要替换的节点为根节点
            root = v;
            return;
        } else if (u == u.parent.left) {
            u.parent.left = v;
        } else {
            u.parent.right = v;
        }
        if (v != null) {
            v.parent = u.parent;
        }
    }


    /**
     * 二插搜素树的递归插入方法
     *
     * @param root       插入的树
     * @param insertData 被插入的数据
     */
    public void insertSortTree(TreeNode<Integer> root, TreeNode<Integer> insertData, TreeNode<Integer> parant) {
        // 插入数据的时候一定需要进行比较，比较的目的是确定插入节点处于当前节点的哪颗子树
        if (root == null) {
            // 当前节点为空节点，直接替换
            root = insertData;
            parant = root.parent;
        }
        if (root.val > insertData.val) {
            // 插入节点在当前子树的左子树
            insertSortTree(root.left, insertData, root);
        } else {
            // 插入节点在当前子树的右子树
            insertSortTree(root.right, insertData, root);
        }
    }


    /**
     * 二叉搜索树节点的旋转
     */
    public boolean leftRotate(TreeNode y) {
        TreeNode x = y.parent;
        if (x != null) {
            y.parent = x.parent;
            if (x.parent != null && x == x.parent.left) {
                y = x.parent.left;
            } else if (x.parent != null && x == x.parent.right) {
                y = x.parent.right;
            }
        }
        x.right = y.left;
        if (y.left != null) {
            // 当y有左子树,防止出现空指针异常
            y.left.parent = x;
        }
        y.left = x;
        x.parent = y;
        return true;
    }

    public boolean rightRotate(TreeNode x) {
        TreeNode y = x.parent;
        if (y != null) {
            x.parent = y.parent;
            if (y.parent != null && y == y.parent.left) {
                x = y.parent.left;
            } else if (y.parent != null && y == y.parent.left) {
                x = y.parent.right;
            }
        }
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }
        x.right = y;
        y.parent = x;
        return true;
    }

    /**
     * 判断二叉树是否是平衡二叉树
     * 自顶向下递归
     *
     * @param root 树的根节点
     * @return 当前树是否为平衡二叉树
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(Height(root.left) - Height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    private int Height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(Height(root.left), Height(root.right)) + 1;
    }

    /**
     * 判断二叉树是否是平衡二叉树
     * 使用自底向上进行递归
     *
     * @param root 树的根节点
     * @return 当前树是否为平衡二叉树
     */
    public boolean isBalancedDownToUp(TreeNode root) {
        return HeightT(root) >= 0;
    }

    private int HeightT(TreeNode root) {
        if (root == null) {
            // 当前树是一颗空树
            return 0;
        }
        int leftHeight = HeightT(root.left);
        int rightHeight = HeightT(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }


    /**
     * 翻转二叉树 : 镜像二叉树
     */

    TreeNode node = new TreeNode();

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        node.val = root.val;
        travel(root, node);
        return node;
    }

    private void travel(TreeNode root, TreeNode node) {
        if (root.right != null) {
            node.left = new TreeNode(root.right.val);
            travel(root.right, node.left);
        }
        if (root.left != null) {
            node.right = new TreeNode(root.left.val);
            travel(root.left, node.right);
        }
    }

    /**
     * 根据树的层序序列创建二叉树
     *
     * @param root : 树的层序遍历数组
     */
    public TreeNode<Integer> constructTreeBySequence(int[] nodes) {
        // 用于层序遍历节点的存储
        Queue<TreeNode> queue = new LinkedList<>();
        // 定位树的非叶子节点数量
        int n = NCBTLen(nodes);
        // System.out.println(n);
        // int nLeaf = (n - 1) / 2; 二叉树非叶子节点数量计算错误
        int nLeaf = (n / 2);
        // System.out.println(nLeaf);
        TreeNode root = new TreeNode(nodes[0]);
        // 动态指针
        int i = 0;
        queue.offer(root);
        while (!queue.isEmpty() && i <= nLeaf) {
            // System.out.println(i);
            // 层序遍历的结果数组中，可以定位当前节点的叶子节点的序号
            // 使用队列存储刚创建完的树的节点
            TreeNode p = queue.poll();
            if (p == null) {
                // 队列可以重复添加null
                // 当节点为空元素的时候直接跳过
                continue;
            }
            if ((2 * i + 1) < n && nodes[2 * i + 1] != -1) {
                // 使用-1对null进行标记
                p.left = new TreeNode(nodes[2 * i + 1]);
            } else {
                // 当前节点左节点为空
                p.left = null;
            }
            queue.offer(p.left);
            if ((2 * i + 2) < nodes.length && nodes[2 * i + 2] != -1) {
                // 使用-1对null进行标记
                p.right = new TreeNode(nodes[2 * i + 2]);
            } else {
                // 当前节点右节点为空
                p.right = null;
            }
            queue.offer(p.right);
            ++i;
        }
        return root;
    }

    /**
     * 测量非完全二叉树中的节点数量
     *
     * @param nodes
     * @return
     */
    private int NCBTLen(int[] nodes) {
        int n = nodes.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (nodes[i] != -1) {
                ++ans;
            }
        }
        return ans;
    }


    /**
     * 记录访问节点路径
     */
    List<TreeNode> t = new ArrayList<>();
    List<TreeNode> f = new ArrayList<>();

    /**
     * 获取给定二叉排序树和给定树中两个节点的最近父节点
     *
     * @param root 根节点
     * @param p    树种节点1
     * @param q    树种节点2
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        find(root, p, t);
        find(root, q, f);
        // 获取两个列表中最开始相同的节点
        return getCommon(t, f);
        // 两个列表都是从根节点开始，如果两个列表的访问路径中，除了根节点外不存在相同的节点，则两个节点的公共祖先就是根节点

    }

    /**
     * 用于获取两个列表的公共父节点
     *
     * @param t 列表1
     * @param f 列表2
     */
    private TreeNode getCommon(List<TreeNode> t, List<TreeNode> f) {
        // 首先移除根节点 root
        TreeNode root = t.remove(0);
        f.remove(0);
        // 默认是th列表中的节点大于fh列表中的节点
        if (t.isEmpty() || f.isEmpty()) {
            return root;
        }
        TreeNode th = t.get(0);
        TreeNode fh = f.get(0);

        while (th.val != fh.val) {
            if (th.val < fh.val) {
                th = t.remove(0);
            } else {
                fh = f.remove(0);
            }
            if (t.isEmpty() || f.isEmpty()) {
                return root;
            }
        }
        while ((!t.isEmpty() && !f.isEmpty()) && (t.get(0).val == f.get(0).val)) {
            th = t.remove(0);
            fh = f.remove(0);
        }
        return th;
    }


    /**
     * 保留一个节点的遍历序列，然后根据这个遍历序列对另一个节点进行搜寻
     * 两个节点的最近父节点为列表中的末尾节点
     */

    public TreeNode lowestCommonAncestorUpdate(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path = new ArrayList<>();
        find(root, p, path);
        TreeNode ans = root;
        TreeNode next = root;
        while (!path.isEmpty()) {
            TreeNode node = path.remove(0);
            if (node.val == next.val) {
                // 要找的两个节点中有一个节点是另一个节点的父节点
                ans = node;
            }
            // 根据当前路径进行寻找
            if (q.val > next.val) {
                next = next.right;
            } else if (q.val < next.val) {
                next = next.left;
            }
        }
        return ans;
    }

    /**
     * 在给定树中存储访问指定节点的路径，存储路径列表t&&f
     *
     * @param root 根节点
     * @param p    查找节点
     * @param list 记录路径的链表
     */
    private void find(TreeNode root, TreeNode p, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        list.add(root);
        if (root.val > p.val) {
            find(root.left, p, list);
        } else if (root.val < p.val) {
            find(root.right, p, list);
        }
    }

    /**
     * 二叉树的层序遍历
     */
    public List<Integer> sequenceSearch(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> auxiliaryQueue = new LinkedList<>();
        auxiliaryQueue.offer(root);
        int layer = 1;
        int nlayer = 0;
        while (!auxiliaryQueue.isEmpty()) {
            TreeNode p = auxiliaryQueue.poll();
            ans.add(p.val);
            layer--;
            if (p.left != null) {
                auxiliaryQueue.offer(p.left);
                ++layer;
            }
            if (p.right != null) {
                auxiliaryQueue.offer(p.right);
                ++layer;
            }
            if (layer == 0) {
                layer = nlayer;
                nlayer = 0;
            }
        }
        return ans;
    }


}
